package com.zhouhong;

/**
 * @ClassName: insert-sort
 * @Description: 插入排序
 * @Author: zhouhong
 * @Create: 2021-03-28 19:38
 **/

public class insertSort {
    private insertSort(){}
    /** 
    * @Description: 插入排序
    * 思路：每次把遍历到的数字放到前面，下一次遍历到的数字放到之前排好序的序列里面的合适位置
    * 外层：i 遍历
    * 内层：j 从 i 开始向前遍历，当 j < j-1 时交换位置，以此类推
    */
    public static <E extends Comparable<E>> void sort1(E[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0 ; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0){
                    swap(arr, j, j - 1);
                }
            }
        }
    }
    /**
    * @Description: 插入排序优化
    * 频繁交换会影响效率，使用一个变量暂存要交换的值，整体平移既可
    */
    public static <E extends Comparable<E>> void sort2(E[] arr){
        for (int i = 0; i < arr.length; i++) {
            E num = arr[i];
            int j;
            for (j = i; j > 0 && num.compareTo(arr[j - 1]) < 0; j--) {
                    arr[j] = arr[j-1];
            }
            arr[j] = num;
        }
    }
    // 换个方法实现插入排序法，我们叫 sort3
    public static <E extends Comparable<E>> void sort3(E[] arr){
        for(int i = arr.length - 1; i >= 0; i --){
            // 将 arr[i] 插入到合适的位置
            E t = arr[i];
            int j;
            for(j = i; j + 1 < arr.length && t.compareTo(arr[j + 1]) > 0; j ++){
                arr[j] = arr[j + 1];
            }
            arr[j] = t;
        }
    }
    private static <E extends Comparable <E>> void swap(E[] arr, int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n:dataSize) {
            Integer[] num = ArrayGenerator.generatorRandomArray(n,n);
            SortingHelper.sortTest("insertSort", num);
        }
    }
}
